home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / RUN.TST / README.RUN < prev    next >
Text File  |  1996-01-10  |  3KB  |  58 lines
  1. DESCRIPTION OF THE RUN TEST
  2.  
  3. Introduction
  4. ------------
  5.  
  6. This implementation of the run test is concerned with "runs up" -
  7. monotone increasing sequences of distinct variates.  Instead of
  8. implementing the "horribly complicated method" [K1, p. 74] of
  9. Knuth's first test, we opted for the "vastly simpler and more
  10. practical run test" [K1, p. 65].  The algorithms used by our
  11. gap test are described in exercises 12 and 14 of Knuth, page 74,
  12. and the answers on page 536.  The algorithm that determines the
  13. length of the runs is implemented in cntruns.c.  The function
  14. that generates the set of distinct variates is genrunda.c.
  15.  
  16. The run test counts lengths of monotone increasing subsequences
  17. (runs up) of an original sequence of distinct variates.  Runs up
  18. of lengths one to five are counted separately.  Runs with lengths
  19. six or higher are lumped together.  The probabilities for the run
  20. lengths and expected counts for 3600 runs are:
  21.  
  22.     Run     Probability     Expected Count
  23.     ---     -----------     --------------
  24.      1         1/2             1800
  25.      2         1/3             1200
  26.      3         1/8              450
  27.      4         1/30             120
  28.      5         1/144             25
  29.      6 (+)     1/720              5
  30.  
  31. To get 3600 runs, which, as you can see, yields an expected count of
  32. five for the least likely run length, about 10,000 distinct variates
  33. must be generated.  To get that many distinct variates about 11931
  34. samples from the uniform generator are required.  This is the mean
  35. number required and it comes with a standard deviation of about 49.5.
  36. To keep the program from "getting stuck" while looking for a complete
  37. set of 10,000 an upper range of 12426 variates is set.  This is the
  38. mean plus 10 standard deviations.  The mean and standard deviation are
  39. calculated in runmnsd.c using formulas from Knuth, page 74, exercise
  40. 10.
  41.  
  42. The run test is implemented as program runtst.exe.  This program
  43. performs a Kolmogorov-Smirnov analysis on probabilities from 100
  44. chi-square tests.  The chi-square statistics are calculated in
  45. genchisq.c;  corresponding probabilities are calculated via calls
  46. to library function chdtr() which is called in the main rpogram,
  47. runtst.c.  Function KSCalc() is called in main() to calculate
  48. Kolmogorov-Smirnov statistics and probabilities.  The parameters
  49. that you specify to execute the run test are:
  50.  
  51.         seed for random number generator
  52.         name of random number generator
  53.         minimum number of events per category (there are six)
  54.  
  55. These parameters are read from the console unless you redirect
  56. the input device.  As usual, prompts and messages are written
  57. to stderr and results are written to stdout.
  58.